package org.movee.jalgo.search;

/**
 * 二叉查找树
 * @param <K>
 */
public class BinarySearchTree<K extends Comparable<K>> {

    private Node<K> root;

    public BinarySearchTree() {
        root = null;
    }

    /**
     * 处理节点
     * @param node 树中的节点
     */
    private void processNode(Node<K> node) {
        System.out.print(node.key + " ");
    }

    private void preOrder(Node<K> node) {
        if (node != null) {
            processNode(node);
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    /**
     * 先序遍历
     */
    public void preOrder() {
        preOrder(root);
    }

    private void inOrder(Node<K> node) {
        if (node != null) {
            inOrder(node.left);
            processNode(node);
            inOrder(node.right);
        }
    }

    /**
     * 中序遍历
     */
    public void inOrder() {
        inOrder(root);
    }

    private void postOrder(Node<K> node) {
        if (node != null) {
            postOrder(node.left);
            postOrder(node.right);
            processNode(node);
        }
    }

    /**
     * 后序遍历
     */
    public void postOrder() {
        postOrder(root);
    }


    private Node<K> search(Node<K> node, K key) {
        if (node == null) {
            return null;
        }

        int cmp = key.compareTo(node.key);
        if (cmp < 0) {
            return search(node.left, key);
        } else if (cmp > 0) {
            return search(node.right, key);
        } else {
            return node;
        }
    }

    /**
     * 递归查找
     * @param key 查找的key
     * @return
     */
    public Node<K> search(K key) {
        checkKeyValidate(key);
        return search(root, key);
    }

    private Node<K> iterativeSearch(Node<K> node, K key) {

        while (node != null) {
            int cmp = key.compareTo(node.key);
            if (cmp < 0) {
                node = node.left;
            } else if (cmp > 0) {
                node = node.right;
            } else {
                return node;
            }
        }

        return node;
    }

    /**
     * 迭代查找
     * @param key 查找的key
     * @return
     */
    public Node<K> iterativeSearch(K key) {
        checkKeyValidate(key);
        return iterativeSearch(root, key);
    }

    private Node<K> minimum(Node<K> node) {
        if (node == null) {
            return null;
        }

        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    /**
     * 最小值
     * @return
     */
    public K minimum() {
        Node<K> p = minimum(root);
        return p == null ? null : p.key;
    }

    private Node<K> maximum(Node<K> tree) {
        if (tree == null) {
            return null;
        }

        while (tree.right != null) {
            tree = tree.right;
        }
        return tree;
    }

    /**
     * 最大值
     * @return
     */
    public K maximum() {
        Node<K> p = maximum(root);
        return p == null ? null : p.key;
    }

    /**
     * 节点的后继
     * @param node
     * @return
     */
    public Node<K> successor(Node<K> node) {
        if (node == null) {
            return null;
        }

        // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
        if (node.right != null) {
            return minimum(node.right);
        }

        // 如果x没有右孩子。则x有以下两种可能：
        // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
        // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
        Node<K> parent = node.parent;
        while ((parent != null) && (node == parent.right)) {
            node = parent;
            parent = parent.parent;
        }

        return parent;
    }

    /**
     * 节点的前驱
     * @param node 节点
     * @return
     */
    public Node<K> predecessor(Node<K> node) {
        // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
        if (node.left != null) {
            return maximum(node.left);
        }

        // 如果x没有左孩子。则x有以下两种可能：
        // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
        // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
        Node<K> parent = node.parent;
        while ((parent != null) && (node == parent.left)) {
            node = parent;
            parent = parent.parent;
        }

        return parent;
    }

    private void insert(Node<K> node) {
        Node<K> parent = null;

        // 插入的位置
        Node<K> tmp = root;
        while (tmp != null) {
            parent = tmp;
            int cmp = node.key.compareTo(tmp.key);
            if (cmp < 0) {
                tmp = tmp.left;
            } else if (cmp > 0) {
                tmp = tmp.right;
            } else {
                // 已存在
                return;
            }
        }

        node.parent = parent;
        if (parent == null) {
            root = node;
        } else {
            int cmp = node.key.compareTo(parent.key);
            if (cmp < 0) {
                parent.left = node;
            } else {
                parent.right = node;
            }
        }
    }

    private void insert(K key) {
        checkKeyValidate(key);
        Node<K> node = new Node<>(key, null, null, null);
        insert(node);
    }

    private void transplant(Node<K> removedNode, Node<K> replaceNode) {

        if (removedNode.parent == null) {
            // 删除的是root节点，替换节点变为root节点
            // root节点的父节点是NIL节点，但NIL节点的孩子并不是root
            root = replaceNode;
        } else if ( removedNode == removedNode.parent.left) {
            // 被删除节点是父节点的左孩子
            removedNode.parent.left = replaceNode;
        } else {
            // 被删除节点是父节点的右孩子
            removedNode.parent.right = replaceNode;
        }
        // 替换节点的父节点调整为被删除节点的父节点
        if (replaceNode != null) {
            replaceNode.parent = removedNode.parent;
        }

    }

    private void delete(Node<K> node) {
        if (node.left == null) {
            transplant(node, node.right);
        } else if (node.right == null) {
            transplant(node, node.left);
        } else {
            Node<K> successor = minimum(node.right);
            if (successor.parent != node) {
                transplant(successor, successor.right);
                successor.right = node.right;
                successor.right.parent = successor;
            }
            transplant(node, successor);
            successor.left = node.left;
            successor.left.parent = successor;
        }
    }

    /**
     * 删除节点
     * @param key
     */
    public void delete(K key) {
        checkKeyValidate(key);
        Node<K> node = search(key);
        if (node != null) {
            delete(node);
        }
    }

    private void checkKeyValidate(K key) {
        if (key == null) {
            throw new IllegalArgumentException("Key must be not null!");
        }
    }


    public static class Node<K extends Comparable<K>> {
        private K key;
        private Node<K> parent;
        private Node<K> left;
        private Node<K> right;


        public Node(K key, Node<K> parent, Node<K> left, Node<K> right) {
            this.key = key;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }

        public String toString() {
            return "" + key;
        }
    }

}
